This invention relates generally to the storage and retrieval of digital data, and more particularly the invention relates to the address of memory whereby data blocks and data words within data blocks can be selectively addressed in normal order or in "bit reversed" or shuffled order for one- and two-dimensional operations.
Zoran Corporation, Assignee of the present application, has introduced a vector signal processor (VSP) designated the ZR34161 whose architecture has been optimized for efficient and rapid computation of digital signal processing operations such as fast Fourier transforms (FFT). As discussed by Rabiner and Gold in Theory and Application of Digital Signal Processing, Prentice Hall, 1975, pp. 363-366, most FFT algorithms including the decimation in time algorithm require that the input sequence of numbers be stored in a shuffled order to provide for the output sequence to be in natural order. For example, the required order of an input sequence is X(0), X(4), X(2), X(6), X(1), X(5), X(3), and finally X(7) to obtain a corresponding output sequence in natural order. When N is a power of 2, the input sequence must be stored in a bit-reversed order for the output to be computed in natural order.
The definition of bit-reversed order is if one forms the L bit binary representation of the natural order indices of the input sequence, where N=2.sup.L, and reverses the bits, the resulting number is the index of the input sequence that belongs in that position. Thus, in the case of N=8=2.sup.3, the natural order indices are shown in the following table at the left side while the bit-reversed indices are shown at the right side:
______________________________________ Normal Order Bit Reversed Order Decimal Binary Binary Mirror Image Decimal ______________________________________ 0 00000 00000 0 1 00001 10000 16 2 00010 01000 8 3 00011 11000 24 4 00100 00100 4 5 00101 10100 20 6 00110 01100 12 7 00111 11100 28 ______________________________________
Thus in order to shuffle the input sequence from its natural to a bit-reversed order, a bit-reversing algorithm is required. One such algorithm is proposed by Rabiner and Gold in which pairs of numbers are interchanged using a temporary storage.